import java.util.Arrays;

public class Solution289 {
    /**
     * 给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。
     * 每个细胞都具有一个初始状态：1 即为活细胞（live），或 0 即为死细胞（dead）。
     * 每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：
     *
     * 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
     * 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
     * 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
     * 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；
     *
     * 根据当前状态，写一个函数来计算面板上所有细胞的下一个（一次更新后的）状态。
     * 下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。
     *
     */
    public void gameOfLife(int[][] board) {
        int rows = board.length;
        if (rows == 0) return;
        int cols = board[0].length;
        int[][] help = new int[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                help[i][j] = board[i][j];
            }
        }
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int num = cellNum(help, i, j);
                if (num < 2) board[i][j] = 0;
                if (num == 2 && help[i][j] ==1) board[i][j] = 1;
                if (num == 3) board[i][j] = 1;
                if (num >3) board[i][j] = 0;
            }
        }
    }

    public int cellNum(int[][] board, int row, int col){
        int[] dx = {-1,  0,  1, -1, 1, -1, 0, 1};
        int[] dy = {-1, -1, -1, 0, 0, 1, 1, 1};
        int sum = 0;
        for (int i = 0; i < 8; i++) {
            int x = row + dx[i];
            int y = col + dy[i];
            if (x >=0 && y>=0 && x < board.length && y < board[0].length){
                sum += board[x][y];
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        Solution289 test = new Solution289();
        int[][] board = {{0,1,0},{0,0,1},{1,1,1},{0,0,0}};
        test.gameOfLife(board);
    }
}
